package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 2/1/21 1:40 PM
 *
 * 路径长度是连续的
 */
public class _05_从二叉树中找到累加和为指定值的最长路径长度 {


    public static int findMaxEqualValLength(TreeNode root, int val) {


        if (root == null) {

            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        return find(root,0,0,val,map);
    }

    public static int find(TreeNode node, int count,int preSum,int val,Map<Integer,Integer> map) {

        if (node == null) {
            return 0;
        }

        int sum = preSum + node.val;

        int beforeVal = sum - val;
        int maxLen = 0;
        if (map.keySet().contains(beforeVal)) {

            int level = map.get(beforeVal);
            maxLen = Math.max(maxLen,count - level);
        }

        boolean flag = false;
        if (!map.keySet().contains(sum)) {

            flag = true;
            map.put(sum,count);
        }

        int leftMaxLen = find(node.left,count+1,sum,val,map);
        int rightMaxLen = find(node.right,count+1,sum,val,map);

        if (flag) {
            map.remove(sum);
        }

        return Math.max(maxLen,Math.max(leftMaxLen,rightMaxLen));
    }

    public static void main(String[] args) {

        /**
         *
         *          3
         *        /  \
         *       1    5
         *       \   / \
         *       2  4  6
         *      / \  \
         *    -10 -20 8
         */
        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);
        //        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(-10);
        root.left.right.right = new TreeNode(-20);
        //        root.left.right.right.right = new TreeNode(-30);
        //        root.left.right.right.right.left = new TreeNode(-40);

        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(6);
        root.right.left.right = new TreeNode(8);

        int maxLen = findMaxEqualValLength(root, 3);

        System.out.println(maxLen);
    }
}
